// btree_logic_test.cpp : Btree unit tests
//

/**
 *    Copyright (C) 2014 MongoDB
 *
 *    This program is free software: you can redistribute it and/or  modify
 *    it under the terms of the GNU Affero General Public License, version 3,
 *    as published by the Free Software Foundation.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU Affero General Public License for more details.
 *
 *    You should have received a copy of the GNU Affero General Public License
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *    As a special exception, the copyright holders give permission to link the
 *    code of portions of this program with the OpenSSL library under certain
 *    conditions as described in each individual source file and distribute
 *    linked combinations including the program with the OpenSSL library. You
 *    must comply with the GNU Affero General Public License in all respects
 *    for all of the code used other than as permitted herein. If you modify
 *    file(s) with this exception, you may extend this exception to your
 *    version of the file(s), but you are not obligated to do so. If you do not
 *    wish to do so, delete this exception statement from your version. If you
 *    delete this exception statement from all source files in the program,
 *    then also delete it in the license file.
 */

// This file contains simple single-threaded tests, which check various aspects of the Btree logic
//

#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kStorage

#include "mongo/db/instance.h"
#include "mongo/db/operation_context_noop.h"
#include "mongo/db/storage/mmap_v1/btree/btree_test_help.h"
#include "mongo/unittest/unittest.h"
#include "mongo/util/log.h"


namespace mongo {

    /**
     * This class is made friend of BtreeLogic so we can add whatever private method accesses we
     * need to it, to be used by the tests.
     */
    template<class BtreeLayoutType>
    class BtreeLogicTestBase {
    public:
        typedef typename BtreeLayoutType::BucketType BucketType;
        typedef typename BtreeLayoutType::FixedWidthKeyType FixedWidthKeyType;

        typedef typename BtreeLogic<BtreeLayoutType>::FullKey FullKey;
        typedef typename BtreeLogic<BtreeLayoutType>::KeyDataOwnedType KeyDataOwnedType;

        BtreeLogicTestBase() : _helper(BSON("TheKey" << 1)) {

        }

        virtual ~BtreeLogicTestBase() {

        }

    protected:
        void checkValidNumKeys(int nKeys) {
            OperationContextNoop txn;
            ASSERT_EQUALS(nKeys, _helper.btree.fullValidate(&txn, NULL, true, false, 0));
        }

        void insert(const BSONObj &key, const DiskLoc dl) {
            OperationContextNoop txn;
            _helper.btree.insert(&txn, key, dl, true);
        }

        bool unindex(const BSONObj &key) {
            OperationContextNoop txn;
            return _helper.btree.unindex(&txn, key, _helper.dummyDiskLoc);
        }

        void locate(const BSONObj &key,
                    int expectedPos,
                    bool expectedFound,
                    const DiskLoc &expectedLocation,
                    int direction) {
            int pos;
            DiskLoc loc;
            OperationContextNoop txn;
            ASSERT_EQUALS(expectedFound,
                          _helper.btree.locate(&txn, key, _helper.dummyDiskLoc, direction, &pos, &loc));
            ASSERT_EQUALS(expectedLocation, loc);
            ASSERT_EQUALS(expectedPos, pos);
        }

        const BucketType* child(const BucketType* bucket, int i) const {
            verify(i <= bucket->n);

            DiskLoc diskLoc;
            if (i == bucket->n) {
                diskLoc = bucket->nextChild;
            }
            else {
                FullKey fullKey = BtreeLogic<BtreeLayoutType>::getFullKey(bucket, i);
                diskLoc = fullKey.prevChildBucket;
            }

            verify(!diskLoc.isNull());

            return _helper.btree.getBucket(NULL, diskLoc);
        }

        BucketType* head() const {
            OperationContextNoop txn;
            return _helper.btree.getBucket(&txn, _helper.headManager.getHead(&txn));
        }

        void forcePackBucket(const DiskLoc bucketLoc) {
            BucketType* bucket = _helper.btree.getBucket(NULL, bucketLoc);

            bucket->topSize += bucket->emptySize;
            bucket->emptySize = 0;
            BtreeLogic<BtreeLayoutType>::setNotPacked(bucket);
        }

        void truncateBucket(BucketType* bucket, int N, int &refPos) {
            _helper.btree.truncateTo(bucket, N, refPos);
        }

        int bucketPackedDataSize(BucketType* bucket, int refPos) {
            return _helper.btree._packedDataSize(bucket, refPos);
        }

        int bucketRebalancedSeparatorPos(const DiskLoc bucketLoc, int leftIndex) {
            BucketType* bucket = _helper.btree.getBucket(NULL, bucketLoc);
            OperationContextNoop txn;
            return _helper.btree._rebalancedSeparatorPos(&txn, bucket, leftIndex);
        }

        FullKey getKey(const DiskLoc bucketLoc, int pos) const {
            const BucketType* bucket = _helper.btree.getBucket(NULL, bucketLoc);
            return BtreeLogic<BtreeLayoutType>::getFullKey(bucket, pos);
        }

        void markKeyUnused(const DiskLoc bucketLoc, int keyPos) {
            BucketType* bucket = _helper.btree.getBucket(NULL, bucketLoc);
            invariant(keyPos >= 0 && keyPos < bucket->n);

            _helper.btree.getKeyHeader(bucket, keyPos).setUnused();
        }

        DiskLoc newBucket() {
            OperationContextNoop txn;
            return _helper.btree._addBucket(&txn);
        }

        /**
         * Sets the nextChild pointer for the bucket at the specified location.
         */
        void setBucketNextChild(const DiskLoc bucketLoc, const DiskLoc nextChild) {
            OperationContextNoop txn;

            BucketType* bucket = _helper.btree.getBucket(&txn, bucketLoc);
            bucket->nextChild = nextChild;

            _helper.btree.fixParentPtrs(&txn, bucket, bucketLoc);
        }

    protected:
        BtreeLogicTestHelper<BtreeLayoutType> _helper;
    };

    //
    // TESTS
    //

    template<class OnDiskFormat>
    class SimpleCreate : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            this->checkValidNumKeys(0);
        }
    };

    template<class OnDiskFormat>
    class SimpleInsertDelete : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            BSONObj key = simpleKey('z');
            this->insert(key, this->_helper.dummyDiskLoc);

            this->checkValidNumKeys(1);
            this->locate(key, 0, true, this->_helper.headManager.getHead(&txn), 1);

            this->unindex(key);

            this->checkValidNumKeys(0);
            this->locate(key, 0, false, DiskLoc(), 1);
        }
    };

    template<class OnDiskFormat>
    class SplitUnevenBucketBase : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            for (int i = 0; i < 10; ++i) {
                BSONObj shortKey = simpleKey(shortToken(i), 1);
                this->insert(shortKey, this->_helper.dummyDiskLoc);

                BSONObj longKey = simpleKey(longToken(i), 800);
                this->insert(longKey, this->_helper.dummyDiskLoc);
            }

            this->checkValidNumKeys(20);
            ASSERT_EQUALS(1, this->head()->n);
            checkSplit();
        }

    protected:
        virtual char shortToken(int i) const = 0;
        virtual char longToken(int i) const = 0;
        virtual void checkSplit() = 0;

        static char leftToken(int i) {
            return 'a' + i;
        }

        static char rightToken(int i) {
            return 'z' - i;
        }
    };

    template<class OnDiskFormat>
    class SplitRightHeavyBucket : public SplitUnevenBucketBase<OnDiskFormat> {
    private:
        virtual char shortToken(int i) const {
            return this->leftToken(i);
        }
        virtual char longToken(int i) const {
            return this->rightToken(i);
        }
        virtual void checkSplit() {
            ASSERT_EQUALS(15, this->child(this->head(), 0)->n);
            ASSERT_EQUALS(4, this->child(this->head(), 1)->n);
        }
    };

    template<class OnDiskFormat>
    class SplitLeftHeavyBucket : public SplitUnevenBucketBase<OnDiskFormat> {
    private:
        virtual char shortToken(int i) const {
            return this->rightToken(i);
        }
        virtual char longToken(int i) const {
            return this->leftToken(i);
        }
        virtual void checkSplit() {
            ASSERT_EQUALS(4, this->child(this->head(), 0)->n);
            ASSERT_EQUALS(15, this->child(this->head(), 1)->n);
        }
    };

    template<class OnDiskFormat>
    class MissingLocate : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            for (int i = 0; i < 3; ++i) {
                BSONObj k = simpleKey('b' + 2 * i);
                this->insert(k, this->_helper.dummyDiskLoc);
            }

            locateExtended(1, 'a', 'b', this->_helper.headManager.getHead(&txn));
            locateExtended(1, 'c', 'd', this->_helper.headManager.getHead(&txn));
            locateExtended(1, 'e', 'f', this->_helper.headManager.getHead(&txn));
            locateExtended(1, 'g', 'g' + 1, DiskLoc()); // of course, 'h' isn't in the index.

            // old behavior
            //       locateExtended( -1, 'a', 'b', dl() );
            //       locateExtended( -1, 'c', 'd', dl() );
            //       locateExtended( -1, 'e', 'f', dl() );
            //       locateExtended( -1, 'g', 'f', dl() );

            locateExtended(-1, 'a', 'a' - 1, DiskLoc()); // of course, 'a' - 1 isn't in the index
            locateExtended(-1, 'c', 'b', this->_helper.headManager.getHead(&txn));
            locateExtended(-1, 'e', 'd', this->_helper.headManager.getHead(&txn));
            locateExtended(-1, 'g', 'f', this->_helper.headManager.getHead(&txn));
        }

    private:
        void locateExtended(
                    int direction, char token, char expectedMatch, DiskLoc expectedLocation) {
            const BSONObj k = simpleKey(token);
            int expectedPos = (expectedMatch - 'b') / 2;

            this->locate(k, expectedPos, false, expectedLocation, direction);
        }
    };

    template<class OnDiskFormat>
    class MissingLocateMultiBucket : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            this->insert(simpleKey('A', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('B', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('C', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('D', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('E', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('F', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('G', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('H', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('J', 800), this->_helper.dummyDiskLoc);

            // This causes split
            this->insert(simpleKey('I', 800), this->_helper.dummyDiskLoc);

            int pos;
            DiskLoc loc;

            // 'E' is the split point and should be in the head the rest should be ~50/50
            const BSONObj splitPoint = simpleKey('E', 800);
            this->_helper.btree.locate(&txn, splitPoint, this->_helper.dummyDiskLoc, 1, &pos, &loc);
            ASSERT_EQUALS(this->_helper.headManager.getHead(&txn), loc);
            ASSERT_EQUALS(0, pos);

            // Find the one before 'E'
            int largePos;
            DiskLoc largeLoc;
            this->_helper.btree.locate(&txn, splitPoint, this->_helper.dummyDiskLoc, 1, &largePos, &largeLoc);
            this->_helper.btree.advance(&txn, &largeLoc, &largePos, -1);

            // Find the one after 'E'
            int smallPos;
            DiskLoc smallLoc;
            this->_helper.btree.locate(&txn, splitPoint, this->_helper.dummyDiskLoc, 1, &smallPos, &smallLoc);
            this->_helper.btree.advance(&txn, &smallLoc, &smallPos, 1);

            ASSERT_NOT_EQUALS(smallLoc, largeLoc);
            ASSERT_NOT_EQUALS(smallLoc, loc);
            ASSERT_NOT_EQUALS(largeLoc, loc);
        }
    };

    /**
     * Validates that adding keys incrementally produces buckets, which are 90%/10% full.
     */
    template<class OnDiskFormat>
    class SERVER983 : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            this->insert(simpleKey('A', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('B', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('C', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('D', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('E', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('F', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('G', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('H', 800), this->_helper.dummyDiskLoc);
            this->insert(simpleKey('I', 800), this->_helper.dummyDiskLoc);

            // This will cause split
            this->insert(simpleKey('J', 800), this->_helper.dummyDiskLoc);

            int pos;
            DiskLoc loc;

            // 'H' is the maximum 'large' interval key, 90% should be < 'H' and 10% larger
            const BSONObj splitPoint = simpleKey('H', 800);
            this->_helper.btree.locate(&txn, splitPoint, this->_helper.dummyDiskLoc, 1, &pos, &loc);
            ASSERT_EQUALS(this->_helper.headManager.getHead(&txn), loc);
            ASSERT_EQUALS(0, pos);

            // Find the one before 'H'
            int largePos;
            DiskLoc largeLoc;
            this->_helper.btree.locate(&txn,
                                splitPoint, this->_helper.dummyDiskLoc, 1, &largePos, &largeLoc);
            this->_helper.btree.advance(&txn, &largeLoc, &largePos, -1);

            // Find the one after 'H'
            int smallPos;
            DiskLoc smallLoc;
            this->_helper.btree.locate(&txn, 
                                splitPoint, this->_helper.dummyDiskLoc, 1, &smallPos, &smallLoc);
            this->_helper.btree.advance(&txn, &smallLoc, &smallPos, 1);

            ASSERT_NOT_EQUALS(smallLoc, largeLoc);
            ASSERT_NOT_EQUALS(smallLoc, loc);
            ASSERT_NOT_EQUALS(largeLoc, loc);
        }
    };

    template<class OnDiskFormat>
    class DontReuseUnused : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            for (int i = 0; i < 10; ++i) {
                const BSONObj k = simpleKey('b' + 2 * i, 800);
                this->insert(k, this->_helper.dummyDiskLoc);
            }

            const BSONObj root = simpleKey('p', 800);
            this->unindex(root);

            this->insert(root, this->_helper.dummyDiskLoc);
            this->locate(root, 0, true, this->head()->nextChild, 1);
        }
    };

    template<class OnDiskFormat>
    class MergeBucketsTestBase : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            for (int i = 0; i < 10; ++i) {
                const BSONObj k = simpleKey('b' + 2 * i, 800);
                this->insert(k, this->_helper.dummyDiskLoc);
            }
            
            // numRecords() - 1, because this->_helper.dummyDiskLoc is actually in the record store too
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL) - 1);

            long long expectedCount = 10 - unindexKeys();
            ASSERT_EQUALS(1, this->_helper.recordStore.numRecords(NULL) - 1);

            long long unusedCount = 0;
            ASSERT_EQUALS(expectedCount, this->_helper.btree.fullValidate(&txn, &unusedCount, true, false, 0));
            ASSERT_EQUALS(0, unusedCount);
        }

    protected:
        virtual int unindexKeys() = 0;
    };

    template<class OnDiskFormat>
    class MergeBucketsLeft : public MergeBucketsTestBase<OnDiskFormat> {
        virtual int unindexKeys() {
            BSONObj k = simpleKey('b', 800);
            this->unindex(k);

            k = simpleKey('b' + 2, 800);
            this->unindex(k);

            k = simpleKey('b' + 4, 800);
            this->unindex(k);

            k = simpleKey('b' + 6, 800);
            this->unindex(k);

            return 4;
        }
    };

    template<class OnDiskFormat>
    class MergeBucketsRight : public MergeBucketsTestBase<OnDiskFormat> {
        virtual int unindexKeys() {
            const BSONObj k = simpleKey('b' + 2 * 9, 800);
            this->unindex(k);
            return 1;
        }
    };

    template<class OnDiskFormat>
    class MergeBucketsDontReplaceHead : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            for (int i = 0; i < 18; ++i) {
                const BSONObj k = simpleKey('a' + i, 800);
                this->insert(k, this->_helper.dummyDiskLoc);
            }

            // numRecords(NULL) - 1, because fixedDiskLoc is actually in the record store too
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL) - 1);

            const BSONObj k = simpleKey('a' + 17, 800);
            this->unindex(k);
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL) - 1);

            long long unusedCount = 0;
            ASSERT_EQUALS(17, this->_helper.btree.fullValidate(&txn, &unusedCount, true, false, 0));
            ASSERT_EQUALS(0, unusedCount);
        }
    };

    template<class OnDiskFormat>
    class MergeBucketsDelInternal : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{d:{b:{a:null},bb:null,_:{c:null}},_:{f:{e:null},_:{g:null}}}");
            ASSERT_EQUALS(8, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "bb");
            verify(this->unindex(k));

            ASSERT_EQUALS(7, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 5 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(6, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{b:{a:null},d:{c:null},f:{e:null},_:{g:null}}");
        }
    };

    template<class OnDiskFormat>
    class MergeBucketsRightNull : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{d:{b:{a:null},bb:null,cc:{c:null}},_:{f:{e:null},h:{g:null}}}");
            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "bb");
            verify(this->unindex(k));

            ASSERT_EQUALS(9, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 5 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(6, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{b:{a:null},cc:{c:null},d:null,f:{e:null},h:{g:null}}");
        }
    };

    // This comment was here during porting, not sure what it means:
    //
    // "Not yet handling this case"
    template<class OnDiskFormat>
    class DontMergeSingleBucket : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{d:{b:{a:null},c:null}}");

            ASSERT_EQUALS(4, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "c");
            verify(this->unindex(k));

            ASSERT_EQUALS(3, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{d:{b:{a:null}}}");
        }
    };

    template<class OnDiskFormat>
    class ParentMergeNonRightToLeft : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{d:{b:{a:null},bb:null,cc:{c:null}},i:{f:{e:null},h:{g:null}}}");

            ASSERT_EQUALS(11, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "bb");
            verify(this->unindex(k));

            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // Child does not currently replace parent in this case. Also, the tree 
            // has 6 buckets + 1 for the this->_helper.dummyDiskLoc.
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{i:{b:{a:null},cc:{c:null},d:null,f:{e:null},h:{g:null}}}");
        }
    };

    template<class OnDiskFormat>
    class ParentMergeNonRightToRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{d:{b:{a:null},cc:{c:null}},i:{f:{e:null},ff:null,h:{g:null}}}");

            ASSERT_EQUALS(11, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "ff");
            verify(this->unindex(k));

            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // Child does not currently replace parent in this case. Also, the tree 
            // has 6 buckets + 1 for the this->_helper.dummyDiskLoc.
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{i:{b:{a:null},cc:{c:null},d:null,f:{e:null},h:{g:null}}}");
        }
    };

    template<class OnDiskFormat>
    class CantMergeRightNoMerge : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{d:{b:{a:null},bb:null,cc:{c:null}},"
                             "dd:null,"
                             "_:{f:{e:null},h:{g:null}}}");

            ASSERT_EQUALS(11, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "bb");
            verify(this->unindex(k));

            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{d:{b:{a:null},cc:{c:null}},"
                                   "dd:null,"
                                   "_:{f:{e:null},h:{g:null}}}");
        }
    };

    template<class OnDiskFormat>
    class CantMergeLeftNoMerge : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{c:{b:{a:null}},d:null,_:{f:{e:null},g:null}}");

            ASSERT_EQUALS(7, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 5 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(6, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "g");
            verify(this->unindex(k));

            ASSERT_EQUALS(6, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 5 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(6, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{c:{b:{a:null}},d:null,_:{f:{e:null}}}");
        }
    };

    template<class OnDiskFormat>
    class MergeOption : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{c:{b:{a:null}},f:{e:{d:null},ee:null},_:{h:{g:null}}}");

            ASSERT_EQUALS(9, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "ee");
            verify(this->unindex(k));

            ASSERT_EQUALS(8, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{c:{b:{a:null}},_:{e:{d:null},f:null,h:{g:null}}}");
        }
    };

    template<class OnDiskFormat>
    class ForceMergeLeft : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{c:{b:{a:null}},f:{e:{d:null},ee:null},ff:null,_:{h:{g:null}}}");

            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "ee");
            verify(this->unindex(k));
            
            ASSERT_EQUALS(9, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{f:{b:{a:null},c:null,e:{d:null}},ff:null,_:{h:{g:null}}}");
        }
    };

    template<class OnDiskFormat>
    class ForceMergeRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{c:{b:{a:null}},cc:null,f:{e:{d:null},ee:null},_:{h:{g:null}}}");

            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 7 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(8, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "ee");
            verify(this->unindex(k));

            ASSERT_EQUALS(9, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{c:{b:{a:null}},cc:null,_:{e:{d:null},f:null,h:{g:null}}}");
        }
    };

    template<class OnDiskFormat>
    class RecursiveMerge : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{h:{e:{b:{a:null},c:null,d:null},g:{f:null}},j:{i:null}}");

            ASSERT_EQUALS(10, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "c");
            verify(this->unindex(k));

            ASSERT_EQUALS(9, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            // Height is not currently reduced in this case
            builder.checkStructure("{j:{g:{b:{a:null},d:null,e:null,f:null},h:null,i:null}}");
        }
    };

    template<class OnDiskFormat>
    class RecursiveMergeRightBucket : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{h:{e:{b:{a:null},c:null,d:null},g:{f:null}},_:{i:null}}");

            ASSERT_EQUALS(9, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "c");
            verify(this->unindex(k));

            ASSERT_EQUALS(8, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{g:{b:{a:null},d:null,e:null,f:null},h:null,i:null}");
        }
    };

    template<class OnDiskFormat>
    class RecursiveMergeDoubleRightBucket : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{h:{e:{b:{a:null},c:null,d:null},_:{f:null}},_:{i:null}}");

            ASSERT_EQUALS(8, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "c");
            verify(this->unindex(k));

            ASSERT_EQUALS(7, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            // no recursion currently in this case
            builder.checkStructure("{h:{b:{a:null},d:null,e:null,f:null},_:{i:null}}");
        }
    };

    template<class OnDiskFormat>
    class MergeSizeTestBase : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        MergeSizeTestBase() : _count(0) {

        }

        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);
            
            const BSONObj& topKey = biggestKey('m');

            DiskLoc leftChild = this->newBucket();
            builder.push(this->_helper.headManager.getHead(&txn), topKey, leftChild);
            _count++;

            DiskLoc rightChild = this->newBucket();
            this->setBucketNextChild(this->_helper.headManager.getHead(&txn), rightChild);

            _count += builder.fillBucketToExactSize(leftChild, leftSize(), 'a');
            _count += builder.fillBucketToExactSize(rightChild, rightSize(), 'n');

            ASSERT(leftAdditional() <= 2);
            if (leftAdditional() >= 2) {
                builder.push(leftChild, bigKey('k'), DiskLoc());
            }
            if (leftAdditional() >= 1) {
                builder.push(leftChild, bigKey('l'), DiskLoc());
            }

            ASSERT(rightAdditional() <= 2);
            if (rightAdditional() >= 2) {
                builder.push(rightChild, bigKey('y'), DiskLoc());
            }
            if (rightAdditional() >= 1) {
                builder.push(rightChild, bigKey('z'), DiskLoc());
            }

            _count += leftAdditional() + rightAdditional();

            initCheck();

            const char *keys = delKeys();
            for (const char *i = keys; *i; ++i) {
                long long unused = 0;
                ASSERT_EQUALS(_count, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));
                ASSERT_EQUALS(0, unused);

                // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
                ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

                const BSONObj k = bigKey(*i);
                this->unindex(k);

                --_count;
            }

            long long unused = 0;
            ASSERT_EQUALS(_count, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));
            ASSERT_EQUALS(0, unused);

            validate();

            if (!merge()) {
                // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
                ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));
            }
            else {
                // The tree has 1 bucket + 1 for the this->_helper.dummyDiskLoc
                ASSERT_EQUALS(2, this->_helper.recordStore.numRecords(NULL));
            }
        }

    protected:
        virtual int leftAdditional() const { return 2; }
        virtual int rightAdditional() const { return 2; }
        virtual void initCheck() {}
        virtual void validate() {}
        virtual int leftSize() const = 0;
        virtual int rightSize() const = 0;
        virtual const char * delKeys() const { return "klyz"; }
        virtual bool merge() const { return true; }

        static BSONObj bigKey(char a) {
            return simpleKey(a, 801);
        }

        static BSONObj biggestKey(char a) {
            int size = OnDiskFormat::KeyMax - bigSize() + 801;
            return simpleKey(a, size);
        }

        static int bigSize() {
            return typename BtreeLogicTestBase<OnDiskFormat>::KeyDataOwnedType(bigKey('a')).dataSize();
        }

        static int biggestSize() {
            return typename BtreeLogicTestBase<OnDiskFormat>::KeyDataOwnedType(biggestKey('a')).dataSize();
        }

        int _count;
    };

    template<class OnDiskFormat>
    class MergeSizeJustRightRight : public MergeSizeTestBase<OnDiskFormat> {
    protected:
        virtual int rightSize() const { 
            return BtreeLogic<OnDiskFormat>::lowWaterMark() - 1; 
        }

        virtual int leftSize() const { 
            return OnDiskFormat::BucketBodySize -
                   MergeSizeTestBase<OnDiskFormat>::biggestSize() -
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType) -
                   (BtreeLogic<OnDiskFormat>::lowWaterMark() - 1);
        }
    };

    template<class OnDiskFormat>
    class MergeSizeJustRightLeft : public MergeSizeTestBase<OnDiskFormat> {
    protected:
        virtual int leftSize() const { 
            return BtreeLogic<OnDiskFormat>::lowWaterMark() - 1;
        }

        virtual int rightSize() const { 
            return OnDiskFormat::BucketBodySize -
                   MergeSizeTestBase<OnDiskFormat>::biggestSize() -
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType) -
                   (BtreeLogic<OnDiskFormat>::lowWaterMark() - 1);
        }

        virtual const char * delKeys() const { return "yzkl"; }
    };

    template<class OnDiskFormat>
    class MergeSizeRight : public MergeSizeJustRightRight<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightRight<OnDiskFormat>::rightSize() - 1; }
        virtual int leftSize() const { return MergeSizeJustRightRight<OnDiskFormat>::leftSize() + 1; }
    };

    template<class OnDiskFormat>
    class MergeSizeLeft : public MergeSizeJustRightLeft<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::rightSize() + 1; }
        virtual int leftSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::leftSize() - 1; }
    };

    template<class OnDiskFormat>
    class NoMergeBelowMarkRight : public MergeSizeJustRightRight<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightRight<OnDiskFormat>::rightSize() + 1; }
        virtual int leftSize() const { return MergeSizeJustRightRight<OnDiskFormat>::leftSize() - 1; }
        virtual bool merge() const { return false; }
    };

    template<class OnDiskFormat>
    class NoMergeBelowMarkLeft : public MergeSizeJustRightLeft<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::rightSize() - 1; }
        virtual int leftSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::leftSize() + 1; }
        virtual bool merge() const { return false; }
    };

    template<class OnDiskFormat>
    class MergeSizeRightTooBig : public MergeSizeJustRightLeft<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::rightSize() + 1; }
        virtual bool merge() const { return false; }
    };

    template<class OnDiskFormat>
    class MergeSizeLeftTooBig : public MergeSizeJustRightRight<OnDiskFormat> {
        virtual int leftSize() const { return MergeSizeJustRightRight<OnDiskFormat>::leftSize() + 1; }
        virtual bool merge() const { return false; }
    };

    template<class OnDiskFormat>
    class MergeRightEmpty : public MergeSizeTestBase<OnDiskFormat> {
    protected:
        virtual int rightAdditional() const { return 1; }
        virtual int leftAdditional() const { return 1; }
        virtual const char * delKeys() const { return "lz"; }
        virtual int rightSize() const { return 0; }
        virtual int leftSize() const { 
            return OnDiskFormat::BucketBodySize -
                   MergeSizeTestBase<OnDiskFormat>::biggestSize() - 
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType);
        }
    };

    template<class OnDiskFormat>
    class MergeMinRightEmpty : public MergeSizeTestBase<OnDiskFormat> {
    protected:
        virtual int rightAdditional() const { return 1; }
        virtual int leftAdditional() const { return 0; }
        virtual const char * delKeys() const { return "z"; }
        virtual int rightSize() const { return 0; }
        virtual int leftSize() const { 
            return MergeSizeTestBase<OnDiskFormat>::bigSize() + 
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType);
        }
    };

    template<class OnDiskFormat>
    class MergeLeftEmpty : public MergeSizeTestBase<OnDiskFormat> {
    protected:
        virtual int rightAdditional() const { return 1; }
        virtual int leftAdditional() const { return 1; }
        virtual const char * delKeys() const { return "zl"; }
        virtual int leftSize() const { return 0; }
        virtual int rightSize() const { 
            return OnDiskFormat::BucketBodySize -
                   MergeSizeTestBase<OnDiskFormat>::biggestSize() - 
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType);
        }
    };

    template<class OnDiskFormat>
    class MergeMinLeftEmpty : public MergeSizeTestBase<OnDiskFormat> {
    protected:
        virtual int leftAdditional() const { return 1; }
        virtual int rightAdditional() const { return 0; }
        virtual const char * delKeys() const { return "l"; }
        virtual int leftSize() const { return 0; }
        virtual int rightSize() const { 
            return MergeSizeTestBase<OnDiskFormat>::bigSize() +
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType);
        }
    };

    template<class OnDiskFormat>
    class BalanceRightEmpty : public MergeRightEmpty<OnDiskFormat> {
    protected:
        virtual int leftSize() const { 
            return OnDiskFormat::BucketBodySize -
                   MergeSizeTestBase<OnDiskFormat>::biggestSize() - 
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType) + 1;
        }

        virtual bool merge() const { return false; }

        virtual void initCheck() {
            OperationContextNoop txn;
            _oldTop = this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson();
        }

        virtual void validate() {
            OperationContextNoop txn;
            ASSERT_NOT_EQUALS(_oldTop,
                              this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson());
        }

    private:
        BSONObj _oldTop;
    };

    template<class OnDiskFormat>
    class BalanceLeftEmpty : public MergeLeftEmpty<OnDiskFormat> {
    protected:
        virtual int rightSize() const { 
            return OnDiskFormat::BucketBodySize -
                   MergeSizeTestBase<OnDiskFormat>::biggestSize() - 
                   sizeof(typename BtreeLogicTestBase<OnDiskFormat>::FixedWidthKeyType) + 1;
        }

        virtual bool merge() const { return false; }

        virtual void initCheck() {
            OperationContextNoop txn;
            _oldTop = this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson();
        }

        virtual void validate() {
            OperationContextNoop txn;
            ASSERT_TRUE(_oldTop != this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson());
        }

    private:
        BSONObj _oldTop;
    };

    template<class OnDiskFormat>
    class BalanceOneLeftToRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$1:null,$2:null,$3:null,$4:null,$5:null,$6:null},"
                                "b:{$20:null,$30:null,$40:null,$50:null,a:null},"
                                "_:{c:null}}");

            ASSERT_EQUALS(14, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x40, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(13, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$6:{$1:null,$2:null,$3:null,$4:null,$5:null},"
                                     "b:{$10:null,$20:null,$30:null,$50:null,a:null},"
                                     "_:{c:null}}");
        }
    };

    template<class OnDiskFormat>
    class BalanceOneRightToLeft : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$1:null,$2:null,$3:null,$4:null},"
                                "b:{$20:null,$30:null,$40:null,$50:null,$60:null,$70:null},"
                                "_:{c:null}}");

            ASSERT_EQUALS(13, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x3, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$20:{$1:null,$2:null,$4:null,$10:null},"
                                      "b:{$30:null,$40:null,$50:null,$60:null,$70:null},"
                                      "_:{c:null}}");
        }
    };

    template<class OnDiskFormat>
    class BalanceThreeLeftToRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$20:{$1:{$0:null},$3:{$2:null},$5:{$4:null},$7:{$6:null},"
                                   "$9:{$8:null},$11:{$10:null},$13:{$12:null},_:{$14:null}},"
                                "b:{$30:null,$40:{$35:null},$50:{$45:null}},"
                                "_:{c:null}}");

            ASSERT_EQUALS(23, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 14 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(15, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x30, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(22, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 14 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(15, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$9:{$1:{$0:null},$3:{$2:null},"
                                            "$5:{$4:null},$7:{$6:null},_:{$8:null}},"
                                     "b:{$11:{$10:null},$13:{$12:null},$20:{$14:null},"
                                            "$40:{$35:null},$50:{$45:null}},"
                                     "_:{c:null}}");
        }
    };

    template<class OnDiskFormat>
    class BalanceThreeRightToLeft : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$20:{$1:{$0:null},$3:{$2:null},$5:null,_:{$14:null}},"
                                "b:{$30:{$25:null},$40:{$35:null},$50:{$45:null},$60:{$55:null},"
                                        "$70:{$65:null},$80:{$75:null},"
                                        "$90:{$85:null},$100:{$95:null}},"
                                "_:{c:null}}");

            ASSERT_EQUALS(25, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 15 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(16, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x5, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(24, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 15 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(16, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$50:{$1:{$0:null},$3:{$2:null},$20:{$14:null},"
                                            "$30:{$25:null},$40:{$35:null},_:{$45:null}},"
                                      "b:{$60:{$55:null},$70:{$65:null},$80:{$75:null},"
                                            "$90:{$85:null},$100:{$95:null}},"
                                      "_:{c:null}}");
        }
    };

    template<class OnDiskFormat>
    class BalanceSingleParentKey : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$1:null,$2:null,$3:null,$4:null,$5:null,$6:null},"
                                "_:{$20:null,$30:null,$40:null,$50:null,a:null}}");

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x40, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(11, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$6:{$1:null,$2:null,$3:null,$4:null,$5:null},"
                                     "_:{$10:null,$20:null,$30:null,$50:null,a:null}}");
        }
    };

    template<class OnDiskFormat>
    class PackEmptyBucket : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null}");

            const BSONObj k = BSON("" << "a");
            ASSERT(this->unindex(k));

            this->forcePackBucket(this->_helper.headManager.getHead(&txn));

            typename BtreeLogicTestBase<OnDiskFormat>::BucketType* headBucket = this->head();

            ASSERT_EQUALS(0, headBucket->n);
            ASSERT_FALSE(headBucket->flags & Packed);

            int unused = 0;
            this->truncateBucket(headBucket, 0, unused);

            ASSERT_EQUALS(0, headBucket->n);
            ASSERT_EQUALS(0, headBucket->topSize);
            ASSERT_EQUALS((int)OnDiskFormat::BucketBodySize, headBucket->emptySize);
            ASSERT_TRUE(headBucket->flags & Packed);
        }
    };

    template<class OnDiskFormat>
    class PackedDataSizeEmptyBucket : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null}");

            const BSONObj k = BSON("" << "a");
            ASSERT(this->unindex(k));

            this->forcePackBucket(this->_helper.headManager.getHead(&txn));

            typename BtreeLogicTestBase<OnDiskFormat>::BucketType* headBucket = this->head();

            ASSERT_EQUALS(0, headBucket->n);
            ASSERT_FALSE(headBucket->flags & Packed);
            ASSERT_EQUALS(0, this->bucketPackedDataSize(headBucket, 0));
            ASSERT_FALSE(headBucket->flags & Packed);
        }
    };

    template<class OnDiskFormat>
    class BalanceSingleParentKeyPackParent : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$1:null,$2:null,$3:null,$4:null,$5:null,$6:null},"
                                "_:{$20:null,$30:null,$40:null,$50:null,a:null}}");

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            // force parent pack
            this->forcePackBucket(this->_helper.headManager.getHead(&txn));

            const BSONObj k = BSON("" << bigNumString(0x40, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(11, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$6:{$1:null,$2:null,$3:null,$4:null,$5:null},"
                                     "_:{$10:null,$20:null,$30:null,$50:null,a:null}}");
        }
    };

    template<class OnDiskFormat>
    class BalanceSplitParent : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree(
                "{$10$10:{$1:null,$2:null,$3:null,$4:null},"
                   "$100:{$20:null,$30:null,$40:null,$50:null,$60:null,$70:null,$80:null},"
                   "$200:null,$300:null,$400:null,$500:null,$600:null,"
                   "$700:null,$800:null,$900:null,_:{c:null}}");

            ASSERT_EQUALS(22, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x3, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(21, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 6 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(7, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$500:{  $30:{$1:null,$2:null,$4:null,$10$10:null,$20:null},"
                                           "$100:{$40:null,$50:null,$60:null,$70:null,$80:null},"
                                           "$200:null,$300:null,$400:null},"
                                       "_:{$600:null,$700:null,$800:null,$900:null,_:{c:null}}}");
        }
    };

    template<class OnDiskFormat>
    class RebalancedSeparatorBase : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree(treeSpec());
            modTree();

            ASSERT_EQUALS(expectedSeparator(),
                          this->bucketRebalancedSeparatorPos(
                                    this->_helper.headManager.getHead(&txn), 0));
        }

        virtual string treeSpec() const = 0;
        virtual int expectedSeparator() const = 0;
        virtual void modTree() {}
    };

    template<class OnDiskFormat>
    class EvenRebalanceLeft : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$7:{$1:null,$2$31f:null,$3:null,"
                                                        "$4$31f:null,$5:null,$6:null},"
                                                   "_:{$8:null,$9:null,$10$31e:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class EvenRebalanceLeftCusp : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { 
            return "{$6:{$1:null,$2$31f:null,$3:null,$4$31f:null,$5:null},"
                     "_:{$7:null,$8:null,$9$31e:null,$10:null}}"; 
        }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class EvenRebalanceRight : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$3:{$1:null,$2$31f:null},_:{$4$31f:null,$5:null,$6:null,$7:null,$8$31e:null,$9:null,$10:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class EvenRebalanceRightCusp : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$4$31f:{$1:null,$2$31f:null,$3:null},_:{$5:null,$6:null,$7$31e:null,$8:null,$9:null,$10:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class EvenRebalanceCenter : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$5:{$1:null,$2$31f:null,$3:null,$4$31f:null},_:{$6:null,$7$31e:null,$8:null,$9:null,$10:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class OddRebalanceLeft : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$6$31f:{$1:null,$2:null,$3:null,$4:null,$5:null},_:{$7:null,$8:null,$9:null,$10:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class OddRebalanceRight : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$4:{$1:null,$2:null,$3:null},_:{$5:null,$6:null,$7:null,$8$31f:null,$9:null,$10:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class OddRebalanceCenter : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$5:{$1:null,$2:null,$3:null,$4:null},_:{$6:null,$7:null,$8:null,$9:null,$10$31f:null}}"; }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class RebalanceEmptyRight : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$a:{$1:null,$2:null,$3:null,$4:null,$5:null,$6:null,$7:null,$8:null,$9:null},_:{$b:null}}"; }
        virtual void modTree() {
            BSONObj k = BSON("" << bigNumString(0xb, 800));
            ASSERT(this->unindex(k));
        }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class RebalanceEmptyLeft : public RebalancedSeparatorBase<OnDiskFormat> {
        virtual string treeSpec() const { return "{$a:{$1:null},_:{$11:null,$12:null,$13:null,$14:null,$15:null,$16:null,$17:null,$18:null,$19:null}}"; }
        virtual void modTree() {
            BSONObj k = BSON("" << bigNumString(0x1, 800));
            ASSERT(this->unindex(k));
        }
        virtual int expectedSeparator() const { return 4; }
    };

    template<class OnDiskFormat>
    class NoMoveAtLowWaterMarkRight : public MergeSizeJustRightRight<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightRight<OnDiskFormat>::rightSize() + 1; }

        virtual void initCheck() {
            OperationContextNoop txn;
            _oldTop = this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson();
        }

        virtual void validate() {
            OperationContextNoop txn;
            ASSERT_EQUALS(_oldTop, this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson());
        }

        virtual bool merge() const { return false; }

    protected:
        BSONObj _oldTop;
    };

    template<class OnDiskFormat>
    class MoveBelowLowWaterMarkRight : public NoMoveAtLowWaterMarkRight<OnDiskFormat> {
        virtual int rightSize() const { return MergeSizeJustRightRight<OnDiskFormat>::rightSize(); }
        virtual int leftSize() const { return MergeSizeJustRightRight<OnDiskFormat>::leftSize() + 1; }

        virtual void validate() {
            OperationContextNoop txn;
            // Different top means we rebalanced
            ASSERT_NOT_EQUALS(this->_oldTop,
                              this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson());
        }
    };

    template<class OnDiskFormat>
    class NoMoveAtLowWaterMarkLeft : public MergeSizeJustRightLeft<OnDiskFormat> {
        virtual int leftSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::leftSize() + 1; }
        virtual void initCheck() {
            OperationContextNoop txn;
            this->_oldTop = this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson();
        }

        virtual void validate() {
            OperationContextNoop txn;
            ASSERT_EQUALS(this->_oldTop,
                          this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson());
        }
        virtual bool merge() const { return false; }

    protected:
        BSONObj _oldTop;
    };

    template<class OnDiskFormat>
    class MoveBelowLowWaterMarkLeft : public NoMoveAtLowWaterMarkLeft<OnDiskFormat> {
        virtual int leftSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::leftSize(); }
        virtual int rightSize() const { return MergeSizeJustRightLeft<OnDiskFormat>::rightSize() + 1; }

        virtual void validate() {
            OperationContextNoop txn;
            // Different top means we rebalanced
            ASSERT_NOT_EQUALS(this->_oldTop,
                              this->getKey(this->_helper.headManager.getHead(&txn), 0).data.toBson());
        }
    };

    template<class OnDiskFormat>
    class PreferBalanceLeft : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$1:null,$2:null,$3:null,$4:null,$5:null,$6:null},"
                              "$20:{$11:null,$12:null,$13:null,$14:null},"
                                "_:{$30:null}}");

            ASSERT_EQUALS(13, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x12, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$5:{$1:null,$2:null,$3:null,$4:null},"
                                   "$20:{$6:null,$10:null,$11:null,$13:null,$14:null},"
                                     "_:{$30:null}}");
        }
    };

    template<class OnDiskFormat>
    class PreferBalanceRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$1:null},"
                              "$20:{$11:null,$12:null,$13:null,$14:null},"
                                "_:{$31:null,$32:null,$33:null,$34:null,$35:null,$36:null}}");

            ASSERT_EQUALS(13, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x12, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{$10:{$1:null},"
                                    "$31:{$11:null,$13:null,$14:null,$20:null},"
                                      "_:{$32:null,$33:null,$34:null,$35:null,$36:null}}");
        }
    };

    template<class OnDiskFormat>
    class RecursiveMergeThenBalance : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:{$5:{$1:null,$2:null},$8:{$6:null,$7:null}},"
                                "_:{$20:null,$30:null,$40:null,$50:null,"
                                    "$60:null,$70:null,$80:null,$90:null}}");

            ASSERT_EQUALS(15, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 5 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(6, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << bigNumString(0x7, 800));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(14, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure(
                "{$40:{$8:{$1:null,$2:null,$5:null,$6:null},$10:null,$20:null,$30:null},"
                   "_:{$50:null,$60:null,$70:null,$80:null,$90:null}}");
        }
    };

    template<class OnDiskFormat>
    class DelEmptyNoNeighbors : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{b:{a:null}}");

            ASSERT_EQUALS(2, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 2 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "a");
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(1, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 1 bucket + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(2, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{b:null}");
        }
    };

    template<class OnDiskFormat>
    class DelEmptyEmptyNeighbors : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,c:{b:null},d:null}");

            ASSERT_EQUALS(4, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 2 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL));

            const BSONObj k = BSON("" << "b");
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(3, this->_helper.btree.fullValidate(&txn, NULL, true, false, 0));

            // The tree has 1 bucket + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(2, this->_helper.recordStore.numRecords(NULL));

            builder.checkStructure("{a:null,c:null,d:null}");
        }
    };

    template<class OnDiskFormat>
    class DelInternal : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,c:{b:null},d:null}");

            long long unused = 0;
            ASSERT_EQUALS(4, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 2 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << "c");
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(3, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 1 bucket + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(2, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            builder.checkStructure("{a:null,b:null,d:null}");
        }
    };

    template<class OnDiskFormat>
    class DelInternalReplaceWithUnused : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,c:{b:null},d:null}");

            const DiskLoc prevChildBucket = 
                            this->getKey(this->_helper.headManager.getHead(&txn), 1).prevChildBucket;
            this->markKeyUnused(prevChildBucket, 0);

            long long unused = 0;
            ASSERT_EQUALS(3, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 2 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(1, unused);

            const BSONObj k = BSON("" << "c");
            ASSERT(this->unindex(k));

            unused = 0;
            ASSERT_EQUALS(2, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 1 bucket + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(2, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(1, unused);

            // doesn't discriminate between used and unused
            builder.checkStructure("{a:null,b:null,d:null}");
        }
    };

    template<class OnDiskFormat>
    class DelInternalReplaceRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,_:{b:null}}");

            long long unused = 0;
            ASSERT_EQUALS(2, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 2 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << "a");
            ASSERT(this->unindex(k));

            unused = 0;
            ASSERT_EQUALS(1, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 1 bucket + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(2, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            builder.checkStructure("{b:null}");
        }
    };

    template<class OnDiskFormat>
    class DelInternalPromoteKey : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,y:{d:{c:{b:null}},_:{e:null}},z:null}");

            long long unused = 0;
            ASSERT_EQUALS(7, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 5 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(6, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << "y");
            ASSERT(this->unindex(k));

            unused = 0;
            ASSERT_EQUALS(6, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            builder.checkStructure("{a:null,e:{c:{b:null},d:null},z:null}");
        }
    };

    template<class OnDiskFormat>
    class DelInternalPromoteRightKey : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,_:{e:{c:null},_:{f:null}}}");

            long long unused = 0;
            ASSERT_EQUALS(4, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << "a");
            ASSERT(this->unindex(k));

            unused = 0;
            ASSERT_EQUALS(3, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 2 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(3, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            builder.checkStructure("{c:null,_:{e:null,f:null}}");
        }
    };

    template<class OnDiskFormat>
    class DelInternalReplacementPrevNonNull : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,d:{c:{b:null}},e:null}");

            long long unused = 0;
            ASSERT_EQUALS(5, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << "d");
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(4, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(1, unused);

            builder.checkStructure("{a:null,d:{c:{b:null}},e:null}");

            // Check 'unused' key
            ASSERT(this->getKey(this->_helper.headManager.getHead(&txn), 1).recordLoc.getOfs() & 1);
        }
    };

    template<class OnDiskFormat>
    class DelInternalReplacementNextNonNull : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{a:null,_:{c:null,_:{d:null}}}");

            long long unused = 0;
            ASSERT_EQUALS(3, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << "a");
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(2, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 3 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(4, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(1, unused);

            builder.checkStructure("{a:null,_:{c:null,_:{d:null}}}");

            // Check 'unused' key
            ASSERT(this->getKey(this->_helper.headManager.getHead(&txn), 0).recordLoc.getOfs() & 1);
        }
    };

    template<class OnDiskFormat>
    class DelInternalSplitPromoteLeft : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:null,$20:null,$30$10:{$25:{$23:null},_:{$27:null}},"
                              "$40:null,$50:null,$60:null,$70:null,$80:null,$90:null,$100:null}");

            long long unused = 0;
            ASSERT_EQUALS(13, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);
            
            const BSONObj k = BSON("" << bigNumString(0x30, 0x10));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            builder.checkStructure("{$60:{$10:null,$20:null,"
                                    "$27:{$23:null,$25:null},$40:null,$50:null},"
                                      "_:{$70:null,$80:null,$90:null,$100:null}}");
        }
    };

    template<class OnDiskFormat>
    class DelInternalSplitPromoteRight : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            ArtificialTreeBuilder<OnDiskFormat> builder(&txn, &this->_helper);

            builder.makeTree("{$10:null,$20:null,$30:null,$40:null,$50:null,$60:null,$70:null,"
                              "$80:null,$90:null,$100$10:{$95:{$93:null},_:{$97:null}}}");

            long long unused = 0;
            ASSERT_EQUALS(13, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            const BSONObj k = BSON("" << bigNumString(0x100, 0x10));
            ASSERT(this->unindex(k));

            ASSERT_EQUALS(12, this->_helper.btree.fullValidate(&txn, &unused, true, false, 0));

            // The tree has 4 buckets + 1 for the this->_helper.dummyDiskLoc
            ASSERT_EQUALS(5, this->_helper.recordStore.numRecords(NULL));
            ASSERT_EQUALS(0, unused);

            builder.checkStructure(
                        "{$80:{$10:null,$20:null,$30:null,$40:null,$50:null,$60:null,$70:null},"
                           "_:{$90:null,$97:{$93:null,$95:null}}}");
        }
    };

    template<class OnDiskFormat>
    class LocateEmptyForward : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            BSONObj key1 = simpleKey('a');
            this->insert(key1, this->_helper.dummyDiskLoc);
            BSONObj key2 = simpleKey('b');
            this->insert(key2, this->_helper.dummyDiskLoc);
            BSONObj key3 = simpleKey('c');
            this->insert(key3, this->_helper.dummyDiskLoc);

            this->checkValidNumKeys(3);
            this->locate(BSONObj(), 0, false, this->_helper.headManager.getHead(&txn), 1);
        }
    };

    template<class OnDiskFormat>
    class LocateEmptyReverse : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            OperationContextNoop txn;
            this->_helper.btree.initAsEmpty(&txn);

            BSONObj key1 = simpleKey('a');
            this->insert(key1, this->_helper.dummyDiskLoc);
            BSONObj key2 = simpleKey('b');
            this->insert(key2, this->_helper.dummyDiskLoc);
            BSONObj key3 = simpleKey('c');
            this->insert(key3, this->_helper.dummyDiskLoc);

            this->checkValidNumKeys(3);
            this->locate(BSONObj(), -1, false, DiskLoc(), -1);
        }
    };

    /* This test requires the entire server to be linked-in and it is better implemented using
       the JS framework. Disabling here and will put in jsCore.

    template<class OnDiskFormat>
    class SignedZeroDuplication : public BtreeLogicTestBase<OnDiskFormat> {
    public:
        void run() {
            ASSERT_EQUALS(0.0, -0.0);
            DBDirectClient c;
            
            static const string ns("unittests.SignedZeroDuplication");

            c.ensureIndex(ns, BSON("b" << 1), true);
            c.insert(ns, BSON("b" << 0.0));
            c.insert(ns, BSON("b" << 1.0));
            c.update(ns, BSON("b" << 1.0), BSON("b" << -0.0));

            ASSERT_EQUALS(1U, c.count(ns, BSON("b" << 0.0)));
        }
    };
    */

/*
// QUERY_MIGRATION: port later
    class PackUnused : public Base {
    public:
        void run() {
            for ( long long i = 0; i < 1000000; i += 1000 ) {
                insert( i );
            }
            string orig, after;
            {
                stringstream ss;
                bt()->shape( ss );
                orig = ss.str();
            }
            vector< string > toDel;
            vector< string > other;
            BSONObjBuilder start;
            start.appendMinKey( "a" );
            BSONObjBuilder end;
            end.appendMaxKey( "a" );
            auto_ptr< BtreeCursor > c( BtreeCursor::make( nsdetails( ns() ),
                                                          id(),
                                                          start.done(),
                                                          end.done(),
                                                          false,
                                                          1 ) );
            while( c->ok() ) {
                bool has_child =
                    c->getBucket().btree()->keyNode(c->getKeyOfs()).prevChildBucket.isNull();

                if (has_child) {
                    toDel.push_back( c->currKey().firstElement().valuestr() );
                }
                else {
                    other.push_back( c->currKey().firstElement().valuestr() );
                }
                c->advance();
            }
            ASSERT( toDel.size() > 0 );
            for( vector< string >::const_iterator i = toDel.begin(); i != toDel.end(); ++i ) {
                BSONObj o = BSON( "a" << *i );
                this->unindex( o );
            }
            ASSERT( other.size() > 0 );
            for( vector< string >::const_iterator i = other.begin(); i != other.end(); ++i ) {
                BSONObj o = BSON( "a" << *i );
                this->unindex( o );
            }

            long long unused = 0;
            ASSERT_EQUALS( 0, bt()->fullValidate(&txn,  dl(), order(), &unused, true ) );

            for ( long long i = 50000; i < 50100; ++i ) {
                insert( i );
            }

            long long unused2 = 0;
            ASSERT_EQUALS( 100, bt()->fullValidate(&txn,  dl(), order(), &unused2, true ) );

//            log() << "old unused: " << unused << ", new unused: " << unused2 << endl;
//
            ASSERT( unused2 <= unused );
        }
    protected:
        void insert( long long n ) {
            string val = bigNumString( n );
            BSONObj k = BSON( "a" << val );
            Base::insert( k );
        }
    };

    class DontDropReferenceKey : public PackUnused {
    public:
        void run() {
            // with 80 root node is full
            for ( long long i = 0; i < 80; i += 1 ) {
                insert( i );
            }

            BSONObjBuilder start;
            start.appendMinKey( "a" );
            BSONObjBuilder end;
            end.appendMaxKey( "a" );
            BSONObj l = bt()->keyNode( 0 ).key.toBson();
            string toInsert;
            auto_ptr< BtreeCursor > c( BtreeCursor::make( nsdetails( ns() ),
                                                          id(),
                                                          start.done(),
                                                          end.done(),
                                                          false,
                                                          1 ) );
            while( c->ok() ) {
                if ( c->currKey().woCompare( l ) > 0 ) {
                    toInsert = c->currKey().firstElement().valuestr();
                    break;
                }
                c->advance();
            }
            // too much work to try to make this happen through inserts and deletes
            // we are intentionally manipulating the btree bucket directly here
            BtreeBucket::Loc* L = const_cast< BtreeBucket::Loc* >( &bt()->keyNode( 1 ).prevChildBucket );
            getDur().writing(L)->Null();
            getDur().writingInt( const_cast< BtreeBucket::Loc& >( bt()->keyNode( 1 ).recordLoc ).GETOFS() ) |= 1; // make unused
            BSONObj k = BSON( "a" << toInsert );
            Base::insert( k );
        }
    };
    */

    //
    // TEST SUITE DEFINITION
    //

    template<class OnDiskFormat>
    class BtreeLogicTestSuite : public unittest::Suite {
    public:
        BtreeLogicTestSuite(const std::string& name) : Suite(name) {

        }

        void setupTests() {
            add< SimpleCreate<OnDiskFormat> >();
            add< SimpleInsertDelete<OnDiskFormat> >();
            add< SplitRightHeavyBucket<OnDiskFormat> >();
            add< SplitLeftHeavyBucket<OnDiskFormat> >();
            add< MissingLocate<OnDiskFormat> >();
            add< MissingLocateMultiBucket<OnDiskFormat> >();
            add< SERVER983<OnDiskFormat> >();
            add< DontReuseUnused<OnDiskFormat> >();
            add< MergeBucketsLeft<OnDiskFormat> >();
            add< MergeBucketsRight<OnDiskFormat> >();
            add< MergeBucketsDontReplaceHead<OnDiskFormat> >();
            add< MergeBucketsDelInternal<OnDiskFormat> >();
            add< MergeBucketsRightNull<OnDiskFormat> >();
            add< DontMergeSingleBucket<OnDiskFormat> >();
            add< ParentMergeNonRightToLeft<OnDiskFormat> >();
            add< ParentMergeNonRightToRight<OnDiskFormat> >();
            add< CantMergeRightNoMerge<OnDiskFormat> >();
            add< CantMergeLeftNoMerge<OnDiskFormat> >();
            add< MergeOption<OnDiskFormat> >();
            add< ForceMergeLeft<OnDiskFormat> >();
            add< ForceMergeRight<OnDiskFormat> >();
            add< RecursiveMerge<OnDiskFormat> >();
            add< RecursiveMergeRightBucket<OnDiskFormat> >();
            add< RecursiveMergeDoubleRightBucket<OnDiskFormat> >();

            add< MergeSizeJustRightRight<OnDiskFormat> >();
            add< MergeSizeJustRightLeft<OnDiskFormat> >();
            add< MergeSizeRight<OnDiskFormat> >();
            add< MergeSizeLeft<OnDiskFormat> >();
            add< NoMergeBelowMarkRight<OnDiskFormat> >();
            add< NoMergeBelowMarkLeft<OnDiskFormat> >();
            add< MergeSizeRightTooBig<OnDiskFormat> >();
            add< MergeSizeLeftTooBig<OnDiskFormat> >();
            add< MergeRightEmpty<OnDiskFormat> >();
            add< MergeMinRightEmpty<OnDiskFormat> >();
            add< MergeLeftEmpty<OnDiskFormat> >();
            add< MergeMinLeftEmpty<OnDiskFormat> >();
            add< BalanceRightEmpty<OnDiskFormat> >();
            add< BalanceLeftEmpty<OnDiskFormat> >();

            add< BalanceOneLeftToRight<OnDiskFormat> >();
            add< BalanceOneRightToLeft<OnDiskFormat> >();
            add< BalanceThreeLeftToRight<OnDiskFormat> >();
            add< BalanceThreeRightToLeft<OnDiskFormat> >();
            add< BalanceSingleParentKey<OnDiskFormat> >();

            add< PackEmptyBucket<OnDiskFormat> >();
            add< PackedDataSizeEmptyBucket<OnDiskFormat> >();

            add< BalanceSingleParentKeyPackParent<OnDiskFormat> >();
            add< BalanceSplitParent<OnDiskFormat> >();
            add< EvenRebalanceLeft<OnDiskFormat> >();
            add< EvenRebalanceLeftCusp<OnDiskFormat> >();
            add< EvenRebalanceRight<OnDiskFormat> >();
            add< EvenRebalanceRightCusp<OnDiskFormat> >();
            add< EvenRebalanceCenter<OnDiskFormat> >();
            add< OddRebalanceLeft<OnDiskFormat> >();
            add< OddRebalanceRight<OnDiskFormat> >();
            add< OddRebalanceCenter<OnDiskFormat> >();
            add< RebalanceEmptyRight<OnDiskFormat> >();
            add< RebalanceEmptyLeft<OnDiskFormat> >();

            add< NoMoveAtLowWaterMarkRight<OnDiskFormat> >();
            add< MoveBelowLowWaterMarkRight<OnDiskFormat> >();
            add< NoMoveAtLowWaterMarkLeft<OnDiskFormat> >();
            add< MoveBelowLowWaterMarkLeft<OnDiskFormat> >();

            add< PreferBalanceLeft<OnDiskFormat> >();
            add< PreferBalanceRight<OnDiskFormat> >();
            add< RecursiveMergeThenBalance<OnDiskFormat> >();
            add< DelEmptyNoNeighbors<OnDiskFormat> >();
            add< DelEmptyEmptyNeighbors<OnDiskFormat> >();
            add< DelInternal<OnDiskFormat> >();
            add< DelInternalReplaceWithUnused<OnDiskFormat> >();
            add< DelInternalReplaceRight<OnDiskFormat> >();
            add< DelInternalPromoteKey<OnDiskFormat> >();
            add< DelInternalPromoteRightKey<OnDiskFormat> >();
            add< DelInternalReplacementPrevNonNull<OnDiskFormat> >();
            add< DelInternalReplacementNextNonNull<OnDiskFormat> >();
            add< DelInternalSplitPromoteLeft<OnDiskFormat> >();
            add< DelInternalSplitPromoteRight<OnDiskFormat> >();

            add< LocateEmptyForward<OnDiskFormat> >();
            add< LocateEmptyReverse<OnDiskFormat> >();
        }
    };

    // Test suite for both V0 and V1
    static BtreeLogicTestSuite<BtreeLayoutV0> SUITE_V0("BTreeLogicTests_V0");
    static BtreeLogicTestSuite<BtreeLayoutV1> SUITE_V1("BTreeLogicTests_V1");
}
